package com.interview.javabasic.Sort;/*
@李子宁
Happy,happy everyday!
冲鸭！
*/

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        //要求将数组进行升序排列
        int arr[] = {4,6,8,5,9};
        heapSort(arr);
    }
    public static void heapSort(int arr[]){
        int tmp = 0;
        System.out.println("堆排序！");
        for (int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        for (int i = arr.length - 1; i > 0 ; i--) {
            //交换
            tmp = arr[i];
            arr[i] = arr[0];
            arr[0] = tmp;
            adjustHeap(arr,0,i);
        }
        System.out.println("数组= "+Arrays.toString(arr));
    }


    //将一个数组(二叉树）调整成一个大顶堆
    //i 非叶子节点的索引
    //length 要调整的元素的个数
    public static void adjustHeap(int arr[],int i, int lenght){
        int tmp = arr[i];//取出当前元素保存临时变量

        for (int k = i*2+1;k<lenght;k = k*2+1){
            if (k+1 < lenght && arr[k] < arr[k+1]){//说明左节店小于有节点的值
                k++;//k指向右子节点
            }
            if(arr[k] > tmp){//子节点大于父节点
                arr[i] = arr[k];//把较大的值赋给当前节点，让i指向k继续循环比较
                i = k;
            }else{
                break;
            }
        }
        arr[i] = tmp;//精tmp放到最后的位置
    }
}
